home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 15664 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.7 KB
  1. Path: winternet.com!not-for-mail
  2. From: jdege@winternet.com (Jeff Dege)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: Fastest Sorting Algorithm?
  5. Date: 6 Apr 1996 19:41:36 GMT
  6. Organization: StarNet Communications, Inc
  7. Message-ID: <4k6hdg$5ob@blackice.winternet.com>
  8. References: <Dou55w.7MB@novice.uwaterloo.ca> <DpAxtI.3w9@undergrad.math.uwaterloo.ca> <4k4unk$15qe@sol.caps.maine.edu> <4k680p$6fs@longwood.cs.ucf.edu>
  9. NNTP-Posting-Host: tundra.winternet.com
  10. X-Newsreader: TIN [UNIX 1.3 950824BETA PL0]
  11.  
  12. On 6 Apr 1996 12:01:13 -0500, Mark Schnitzius (schnitzi@longwood.cs.ucf.edu) wrote:
  13. : 
  14. : Is it really 2logn?  My understanding was that a sort couldn't be
  15. : less than nlogn...  More info, please.
  16.  
  17.     No sort that works on comparing elements can be less than O(n*log(n)).
  18. There are sorts that don't work by comparing elements that can do better
  19. than this, but are restricted in the types of elements they can sort.
  20. You'll find these in the texts as radix or bucket sorts.
  21.  
  22.     The fastest sort of all uses a different trick altogether.  It's
  23. the TrickSort:
  24.  
  25. Input:  an array A of n integers with arbitrary ordering.
  26. Result: an array A of n integers ordered such that A[i] <= A[i+1] for
  27. all i in [0, n-1).
  28.  
  29. Solution:
  30.  
  31. trickSort(int A[], int size)
  32. {
  33.     int i;
  34.  
  35.     for (i=0; i<size; i++)
  36.         A[0] = 0;
  37. }
  38.  
  39. -- 
  40.         "I quite agree with you," said the Duchess; "and the moral of
  41. that is -- `Be what you would seem to be' -- or, if you'd like it put
  42. more simply -- `Never imagine yourself not to be otherwise than what it
  43. might appear to others that what you were or might have been was not
  44. otherwise than what you had been would have appeared to them to be
  45. otherwise.'"
  46.                 -- Lewis Carrol, "Alice in Wonderland"
  47.  
  48.  
  49.